class Solution
{
public:
    // 暴力dfs 超时
    int numberOfGoodPaths(vector<int> &vals, vector<vector<int>> &edges)
    {
        int n = vals.size();
        vector<vector<int>> adjacentTable(n, vector<int>{});
        for (auto edge : edges)
        {
            adjacentTable[edge[0]].push_back(edge[1]);
            adjacentTable[edge[1]].push_back(edge[0]);
        }
        unordered_map<int, int> valCount;
        for (int val : vals)
        {
            ++valCount[val];
        }
        vector<int> usedAsEndCount(n, 0);
        vector<int> usedAsStart(n, 0);
        int totalPathCount = 0;
        for (int i = 0; i < n; ++i)
        {
            if (usedAsEndCount[i] == (valCount[vals[i]] - 1))
            {
                continue;
            }
            queue<int> q;
            int val = vals[i];
            unordered_set<int> seen;
            seen.insert(i);
            q.push(i);
            while (!q.empty())
            {
                int node = q.front();
                q.pop();
                for (int adjacentNode : adjacentTable[node])
                {
                    if (seen.count(adjacentNode))
                    {
                        continue;
                    }
                    if (vals[adjacentNode] == val)
                    {
                        if (!usedAsStart[adjacentNode])
                        {
                            ++totalPathCount;
                        }
                        ++usedAsEndCount[adjacentNode];
                        q.push(adjacentNode);
                    }
                    else if (vals[adjacentNode] < val)
                    {
                        q.push(adjacentNode);
                    }
                    seen.insert(adjacentNode);
                }
            }
            usedAsStart[i] = 1;
        }
        totalPathCount += n;
        return totalPathCount;
    }
};